/**
 * @brief 二分查找--迭代法
 * @param arr 待查找的数组
 * @param size 数组的大小
 * @param target 待查找的元素
 * @return 返回代查找元素的索引，否则返回-1
 */
int binarySearch_iterative(int arr[], int size, int target)
{
    // 创建三个变量，一个存储第一个数组的索引，一个存储最后一个数组的索引。
    // 还有一个变量是专门用来存储中间元素的索引(这个变量需要再循环里边创建)，
    // 用来确定查找数组的左半边还是右半边
    int low = 0;
    int high = size - 1;
    while (low <= high)
    {
        // 获得中间元素的索引
        int mid = low + (high - low) / 2;
        // 检查中间值是不是目标值
        if (arr[mid] == target)
        {
            return mid;
        }
        // 如果目标值比中间值还要大就将将low的值改成mid+1锁定数组的右边部分
        // 如果目标值比中间值小，就修改high的值是mid+1,锁定数组的左半部分
        // 这两步操作放到两个判断里边
        if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    // 如果循环结束都没有找到target，直接返回-1
    return -1;
}
/**
 * @brief 使用递归法来实现二分查找法
 * @param arr 待查找的数组
 * @param size 数组大小
 * @param target 待查找的元素
 * @return 返回目标元素的索引，否则返回-1
 */
int binarySearch_recursive(int arr[], int low, int high, int target)
{
    // 前提条件，需要判断low是不是严格小于等于high，
    // 如果不是就退出这个函数
    if (low <= high)
    {
        int mid = low + (high - low) / 2;
        // 如果中间元素就是目标元素，就返回这个索引
        if (arr[mid] == target)
        {
            return mid;
        }
        if (arr[mid] < target)
        {
            return binarySearch_recursive(arr, mid + 1, high, target);
        }
        else
        {
            return binarySearch_recursive(arr, low, mid - 1, target);
        }
    }
    return -1;
}